package com.hspedu.search;

import java.util.Arrays;

/**
 * Created by Gening on 30/10/2025
 */
public class FibonacciSearch {
    public static int maxSize=20;

    public static void main(String[] args) {
        int [] arr ={1,8, 10,89,1000,1234};

        int i = fibSearch(arr, 1000);
        System.out.println("the element is =" + i);

    }
    //获取一个数列 mid=low+F(k-1)-1
     public static int[] fib(){
        int [] f = new int[maxSize];
        f[0]=1;
        f[1]=1;
         for (int i = 2; i < maxSize; i++) {
             f[i]= f[i-1]+f[i-2];
         }
         return f;
     }

     public static int fibSearch(int arr[], int key){
        int low = 0;
        int high= arr.length-1;
        int k = 0; // fibonacci 数值下标
        int mid = 0;
        int f[] = fib();

        while (high>f[k]-1){
            k++;
        }
        //f[k]可能大于数组的长度，构建一个新的数组，不足部分用0进行填充，并且指向temp
         int[] temp = Arrays.copyOf(arr,f[k]);
         for(int i= high+1 ;i<temp.length;i++){
             temp[i]=arr[high];
         }

         // 使用while循环找到我们的key
         while(low<=high){
             mid= low + f[k-1]-1;
             if(key<temp[mid]){
                 high=mid-1;
                 k--;
             }else if(key>temp[mid]){
                 low=mid+1;
                 k-=2;
             }else {
                 if(mid<=high){
                     return mid;
                 }else {
                     return high;
                 }
             }

         }
         return -1;



     }



}
